Very Efficient Training of Convolutional Neural Networks using Fast Fourier Transform and Overlap-and-Add

摘要

Convolutional neural networks (CNNs) are currently state-of-the-art forvarious classification tasks, but are computationally expensive. Propagatingthrough the convolutional layers is very slow, as each kernel in each layermust sequentially calculate many dot products for a single forward and backwardpropagation which equates to $\mathcal{O}(N^{2}n^{2})$ per kernel per layerwhere the inputs are $N \times N$ arrays and the kernels are $n \times n$arrays. Convolution can be efficiently performed as a Hadamard product in thefrequency domain. The bottleneck is the transformation which has a cost of$\mathcal{O}(N^{2}\log_2 N)$ using the fast Fourier transform (FFT). However,the increase in efficiency is less significant when $N\gg n$ as is the case inCNNs. We mitigate this by using the "overlap-and-add" technique reducing thecomputational complexity to $\mathcal{O}(N^2\log_2 n)$ per kernel. This methodincreases the algorithm's efficiency in both the forward and backwardpropagation, reducing the training and testing time for CNNs. Our empiricalresults show our method reduces computational time by a factor of up to 16.3times the traditional convolution implementation for a 8 $\times$ 8 kernel anda 224 $\times$ 224 image.